
// Copyright (C) 2007 Richard Uhler
// This file is part of Esiply.
//
// Esiply is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License, Version 2,
// as published by the Free Software Foundation.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

// This file contains the implementation for all the Array standard
// library stuff that can be implemented completely in javascript.

// Ecma 15.4.1.1 Array ([item1[,itme2[,...]]])
// The Array constructor called as a function is the same
// as calling it as a constructor, so we only have the one function
// for both cases.
// 
// Ecma 15.4.2.1 new Array ([item1[,itme2[,...]]])
Esiply.set_attributes(this, "Array", Esiply.DONT_ENUM);
Array = function()
{
    // Ecma 15.4.2.1 new Array([item0[,item1[,...]]])
    var obj = [];
    if (arguments.length != 1)
    {
        // The length property of the newly constructed object is set
        // to the number of arguments.
        obj.length = arguments.length;

        for (var i = 0; i < arguments.length; i++)
        {
            obj[i] = arguments[i];
        }
    }
    else
    {
        var len = arguments[0];
        if (typeof len == "number" && len == (len >>> 0))
        {
            // If the argument len is a Number and toUint32(len) is equal
            // to len, then the length property of the newly constructed
            // object is set to toUint32(len).
            obj.length = len >>> 0;
        }
        else if (typeof len == "number")
        {
            // If len is a number and toUint32(len) doesn't equal len,
            // throw a RangeError.
            throw new RangeError("Array: length is not in range");
        }
        else
        {
            // If len isn't a number, then the length property is set to
            // 1, and the 0 property is set to len
            obj.length = 1;
            obj[0] = len;
        }
    }
    return obj;
};

// Ecma 15.4.3.1 Array.prototype
// The initial value of Array.prototype is the Array prototype object.
// This property has the attributes {DontEnum, DontDelete,ReadOnly}.
Array.prototype = Esiply.array_prototype;
Esiply.set_attributes(Array, "prototype",
        Esiply.DONT_ENUM | Esiply.DONT_DELETE | Esiply.READ_ONLY);

// Ecma 15.4.4.1 Array.prototype.constructor
// The initial value of Array.prototoype.constructor is the built-in Array
// constructor
Esiply.set_attributes(Array.prototype, "constructor", Esiply.DONT_ENUM);
Array.prototype.constructor = Array;

// Ecma 15.4.4.2 Array.prototype.toString()
// The result of calling this function is the same as if the built-in join
// method were invoked for this object with no argument
// The toString function is not generic; it throws a TypeError exception
// if its this value is not an Array object. Therefore, it cannot
// be transferred to other kinds of objects for use as a method
Esiply.set_attributes(Array.prototype, "toString", Esiply.DONT_ENUM);
Array.prototype.toString = function()
{
    if (Esiply.get_class(this) != "Array")
    {
        throw new TypeError("Non-Array as this of Array.prototype.toString");
    }
    return this.join();
};

// Ecma 15.4.4.3 Array.prototype.toLocaleString()
// The elements of the array are converted to strings using their
// toLocaleString methods, and these strings are then concatenated,
// separated by occurrences of a separator string that has been
// derived in an implementation-defined locale-specific way. The result
// of calling this function is intended to be analogous to the result of
// toString, except that the result of this function is intended to be
// localespecific
Esiply.set_attributes(Array.prototype, "toLocaleString", Esiply.DONT_ENUM);
Array.prototype.toLocaleString = function()
{
    // This is just like the Array.prototype.join function except that
    // we have to choose our own local specific separator, and we call
    // toLocaleString on the elements instead of toString

    // TODO: what should the separator be?
    var separator = ",";

    // undefined and null are converted to the empty string.
    function tostr(x)
    {
        return (x == undefined || x == null) ? "" : x.toLocaleString();
    }
        
    var str = "";
    if (this.length > 0)
    {
        str += tostr(this[0]);
    }
    for (var i = 1; i < this.length; i++)
    {
        str += separator + tostr(this[i]);
    }
    return str;
};

// Ecma 15.4.4.4 Array.prototoype.concat([item1[,item2[,...]]])
// As far as I can tell, concat returns an array which is the concatenation
// of all arguments (including this), where any array arguments are
// flattened out to the first level.
Esiply.set_attributes(Array.prototype, "concat", Esiply.DONT_ENUM);
Array.prototype.concat = function(obj)
{
    function cat_one(dst, src)
    {
        // if src is an array, flatten it, and add them individually
        // otherwise just push x
        if (src instanceof Array)
        {
            for (var i = 0; i < src.length; i++)
            {
                dst.push(src[i]);
            }
        }
        else
        {
            dst.push(src);
        }
    }
           
    var res = new Array();

    // Add this
    cat_one(res, this);

    // Add the rest
    for (var i = 0; i < arguments.length; i++)
    {
        cat_one(res, arguments[i]);
    }
    return res;
};

// Ecma 15.4.4.5 Array.prototype.join(separator)
// The elements of the array are converted to strings, and these strings
// are then concatenated, separated by occurrences of separator. If no
// separator is provided, a single comma is used as the separator.
Esiply.set_attributes(Array.prototype, "join", Esiply.DONT_ENUM);
Array.prototype.join = function(separator)
{
    // If separator is undefined, let it be ","
    if (separator == undefined)
    {
        separator = ",";
    }

    // Convert separator to a string
    separator = "" + separator;

    // undefined and null are converted to the empty string.
    function tostr(x)
    {
        return (x == undefined || x == null) ? "" : "" + x;
    }
        
    var str = "";
    if (this.length > 0)
    {
        str += tostr(this[0]);
    }
    for (var i = 1; i < this.length; i++)
    {
        str += separator + tostr(this[i]);
    }
    return str;
};


// Ecma 15.4.4.6 Array.prototype.pop()
// The last element in the array is removed from the array and returned.
// If there is no element, undefined is returned.
Esiply.set_attributes(Array.prototype, "pop", Esiply.DONT_ENUM);
Array.prototype.pop = function()
{
    var len = this.length;
    if (len == 0)
    {
        return undefined;
    }
    len--;
    var result = this[len];
    delete this[len];
    this.length = len;
    return result;
};

// Ecma 15.4.4.7 Array.prototype.push([item1[,item2[,...]]])
// Add each of the items to the end of this array. Return the new
// array's length
Esiply.set_attributes(Array.prototype, "push", Esiply.DONT_ENUM);
Array.prototype.push = function(obj)
{
    var len = this.length;
    for (var i = 0; i < arguments.length; i++)
    {
        this[i + len] = arguments[i];
    }
    this.length = len + arguments.length;
    return this.length;
};

// Ecma 15.4.4.8 Array.prototype.reverse()
// The elements of the array are rearranged so as to reverse their order.
// The object is returned as the result of the call
Esiply.set_attributes(Array.prototype, "reverse", Esiply.DONT_ENUM);
Array.prototype.reverse = function()
{
    var temp;
    for (var i = 0; i < this.length-i-1; i++)
    {
        temp = this[i];
        this[i] = this[this.length-i-1];
        this[this.length-i-1] = temp;
    }
    return this;
};

// Ecma 15.4.4.9 Array.prototype.shift()
// The first element of the array is removed from the array and returned.
Esiply.set_attributes(Array.prototype, "shift", Esiply.DONT_ENUM);
Array.prototype.shift = function()
{
    // 1. Call the [[get]] method of this object with arguments "length"
    // 2. Call toUint32 on that
    var length = this.length >>> 0;

    // 3. If that's not zero, go to step 6
    if (length == 0)
    {
        // 4. Call the put method with args length and res(2)
        this.length = length;

        // 5. Return undefined.
        return undefined;
    }

    // 6. Call the [[get]] method of this object with arg0
    var at0 = this[0];

    // 7. Let k be 1
    // 8. If k equals length, go to step 18.
    for (var k = 1; k < length; k++)
    {
        // 9. Call toString(k)
        var kstr = String(k);

        // 10. Call toString(k-1)
        var km1str = String(k-1);

        // 11. If this object has a property named by kstr, go to step 12;
        // but if this object has no property named by kstr, then go to step 15
        if (kstr in this)
        {
            // 12. Call the get method of this with kstr
            // 13. Call the put method with args res10, res 12
            // 14. go to step 16.
            this[km1str] = this[kstr];

        }
        else
        {
            // 15. Call the [[delete]] method of this object with arg km1str
            delete this[km1str];
        }

        // 16. Increase K by 1
        // 17. go to step 8
    }

    // 18. Call the [[delete]] method of this object with args length-1
    delete this[String(length-1)];

    // 19. Call the put method with args length-1
    this.length = String(length-1);

    // 20. Return result 6
    return at0;
};

// Ecma 15.4.4.10 Array.prototype.slice(start, end)
// The slice method takes two arguments, start and end, and returns an
// array containing the elements of the array from element start up to,
// but not including, element end (or through the end of the array if
// end is undefined). If start is negative, it is treated as (length+start) 
// where length is the length of the array. If end is negative, it is treated
// as (length+end) where length is the length of the array.
Esiply.set_attributes(Array.prototype, "slice", Esiply.DONT_ENUM);
Array.prototype.slice = function(start, end)
{
    // 1. Let A be a new array created as if by the expression new Array().
    var A = new Array();

    // 2. Call the [[get]] method with arg length
    // 3. Call uint32 of that
    var length = this.length >>> 0;

    // 4. Call toInteger(start)
    start = Math.floor(start);

    // 5. If result is negative, use max((res3+res4), 0);
    // else use min(res4,res3).
    // 6. Let k be that result
    var k = start < 0 ? Math.max((length+start), 0) : Math.min(start, length);

    // 7. If end is undefined, use res3, else use toInteger(end)
    end = (end == undefined) ? length : Math.floor(end);

    // 8. If result7 is negative, use max((res3+res7), 0); else use
    // min(res7,res3);
    end = (end < 0) ? Math.max(length + end, 0) : Math.min(end, length);

    // 9. Let n be 0
    var n = 0;

    // 10. If k is greater than or equal to end, go to step 19.
    while (k < end)
    {
        // 11. Call toString k
        var kstr = String(k);

        // 12. If this object has a property named by kstr, go to step 13; but
        // if this object has no property named by that, go to 16.
        if (kstr in this)
        {
            // 13 Call toStringn
            var nstr = String(n);

            // 14. Call the [[get]] method of this object with arg kstr.
            // 15. call the [[put]] method of A with arguments res13, res14
            A[nstr] = this[kstr];
        }

        // 16 Increase k by 1
        k++;

        // 17 Increase n by 1
        n++;

        // 18. Go to step 10
    }

    // 19 Call the put method of A with args length and n
    A.length = n;

    // 20 Return A.
    return A;
};

// Ecma 15.4.4.11 Array.prototype.sort(comparefn)
// The elements of the array are sorted. If comparefn is not
// undefined, it should be a function that accepts to arguments x and y
// and returns a negative value if x < y, zero if x = y, or a 
// positive value if x > y.
Esiply.set_attributes(Array.prototype, "sort", Esiply.DONT_ENUM);
Array.prototype.sort = function(comparefn)
{
    // This is rather nebulous. I'm just going to sort the array, and
    // hopefully it will comply with the spec.

    var SortCompare = function(obj, j, k)
    {
        // 1. Call toString(j);
        var jstr = String(j);

        // 2. Call toString(k);
        var kstr = String(k);

        // 3. If this object does not have a property named by jstr, and
        // this object does not have a property named by kstr, return +0
        if (!(jstr in obj) && !(kstr in obj))
        {
            return +0;
        }

        // 4. If this object does not have a property named by res1, return 1
        if (!(jstr in obj))
        {
            return 1;
        }

        // 5. If this object does not have a property named by res2, return -1
        if (!(kstr in obj))
        {
            return -1;
        }

        // 6. Call the [[get]] method of obj with res1
        // 8. Let x be that result
        var x = obj[jstr];

        // 7. Call the [[get]] method of obj with res2
        // 9. Let y be that result
        var y = obj[kstr];

        // 10. If x and y are both undefined, return +0
        if (typeof x == "undefined" && typeof y == "undefined")
        {
            return +0;
        }

        // 11. If x is undefined, return 1.
        if (typeof x == "undefined")
        {
            return 1;
        }

        // 12. If y is undefined, return -1
        if (typeof y == "undefined")
        {
            return -1;
        }

        // 13. If the argument comparefn is undefined, go to step 16.
        if (typeof comparefn != "undefined")
        {
            // 14. Call comparefn with args x and y
            // 15. return that result
            return comparefn(x, y);
        }

        // 16. Call toString(x)
        x = String(x);

        // 17. Call toString(y)
        y = String(y);

        // 18. If res16 < res17, return -1.
        if (x < y)
        {
            return -1;
        }

        // 19. If res16 > res17, return 1.
        if (x > y)
        {
            return 1;
        }

        // 20. ret +0.
        return +0;
    };

    debug("SORTING: " + this.join() + "\n");

    var length = this.length >>> 0;
    if (length < 2)
    {
        return;
    }

    var mid = Math.floor(length/2);
    
    //  TODO: this should use Function.apply, or something like that
    // because this might not be an array, and thus not have a slice
    // method.
    var left = this.slice(0, mid);
    left.sort();
    debug("LEFT: " + left.join() + "\n");

    var right = this.slice(mid, length);
    right.sort();
    debug("Right: " + right.join() + "\n");

    var li = 0;
    var ri = mid;
    var ti = 0;

    left = left.concat(right);
    debug("CATED: " + left.join() + "\n");
    while (li < mid && ri < length)
    {
        this[ti++] = SortCompare(left, li, ri) < 0 ? left[li++] : left[ri++];
    }
    while (li < mid)
    {
        this[ti++] = left[li++];
    }
    while (ri < length)
    {
        this[ti++] = left[ri++];
    }
    debug("MERGED: " + this.join() + "\n");
};

// Ecma 15.5.4.12 Array.prototype.splice(start, deleteCount[,item1[,[,...]])
// When the splice method is called with two or more arguments start,
// deleteCount and (optionally) item1, item2, etc., the deleteCount elements
// of the array starting at array index start are replaced by the arguments
// item1, item2, etc.
Esiply.set_attributes(Array.prototype, "splice", Esiply.DONT_ENUM);
Array.prototype.splice = function(start, deleteCount)
{
    // 1. Let A be a new array created as if by the expression new Array().
    var A = new Array();

    // 2. Call the [[get]] method of this object with args length
    // 3. Call toUint32 on that
    var len = this.length >>> 0;

    // 4. Call toInteger(start)
    start = Math.floor(start);

    // 5. If result 4 is negative, use max((res3+res4),0), else use
    // min(res4,res3)
    var base = start < 0 ? Math.max(len + start, 0) : Math.min(start, len);

    // 6. Compute min(max(toint(deleteCount),0),res3-res5)
    var count = Math.min(Math.max(Math.floor(deleteCount), 0), len-base);
    debug("splice: start(" + start + "), len(" + len + "), base(" + base + "), count(" + count + ")\n");

    // 7. Let k be 0
    // 8. If k equals res6, go to step 16
    for (var k = 0; k < count; k++)
    {
        // 9. Call toString(res5+k)
        var istr = String(base+k);

        // 10. If this object has a property named by istr, go to step 11;
        // but if this object has no property named by res9, then go to step 14
        if (istr in this)
        {
            // 11. Call toString(k)
            var kstr = String(k);

            // 12. Call the [[get]] method of this object with arg res9
            // 13. Call the [[put]] method of A with args res11, res12
            A[kstr] = this[istr];
        }

        // 14. Increment k by 1
        // 15. Go to step 8.
    }

    // 16. Call the [[put]] method of A with args "length" and res6
    A.length = count;

    // 17. Compute the number of additional args item1, item2, etc.
    var addargs = arguments.length-2;

    // 18. If res 17 is equal to res6, go to step 48
    // 19. If res 17 is greater than res6, go to step 37
    if (addargs < count)
    {
        // 20. Let k be result 5
        // 21. If k is equal to res3-res6, go to step 31
        for(var k = base; k != len - count; k++)
        {
            // 22. Call toString(k+res6)
            var res22 = String(k+base);

            // 23. Call toString(k+res17)
            var res23 = String(k+addargs);

            // 24. If this object has a property named by Result22, go to
            // step 25, but if not, go to step 28
            if (res22 in this)
            {
                // 25. Call the [[get]] method of this object with args res22
                // 26. Call the put method of this object with args res23, 25
                this[res23] = this[res22];

                // 27. Go to step 29
            }
            else
            {
                // 28 Call the delete method of this object with args res23
                delete this[res23];
            }

            // 29. increase k by 1
            // 30. go to step 21.
        }

        // 31. Let k be res3
        // 32. if k is equal to res3-res6+res17, go to step 48
        for (k = len; k != len - count + addargs; k--)
        {

            // 33. Call toString(k-1)
            // 34. Call the [[delete]] method of this obj with that result
            delete this[String(k-1)];

            // 35. Decrement k by 1
            // 36. Go to step 32
        }
    }
    else if (addargs > count)
    {
        // 37. let k be res3-res6
        // 38. if k is equal to result 5, go to step 49
        for (k = len - count; k != base; k--)
        {
            // 39. Call toString(k+res6-1)
            var res39 = String(k+count-1);

            // 40. Call toString(k+res17-1)
            var res40 = String(k+addargs-1);

            // 41. If this object has a property named by res39, go to
            // step 42; but if this object has no property named by res39,
            // then go to step 45
            if (res39 in this)
            {
                // 42. Call the [[get]] method of this with arg res39
                // 43. Call the [[put]] method of this with 40, 42
                this[res40] = this[res39];

                // 44. Go to step 46.
            }
            else
            {
                // 45. Call the [[delete]] method of this obj with res40
                delete this[res40];
            }

            // 46. Decrease k by 1
        }

        // 47. Go to step 38
    }

    // 48. Let k be result 5
    // 49 Get the next argument in the part of the arg list that starts
    // with item1; if there are no more args, go to step 53.
    for (k = base; k < addargs+base; k++)
    {
        // 50. Call the [[put]] method of this object with toString(k) and
        // res 49
        this[String(k)] = arguments[k-base+2];

        // 51. Increment k by 1
        // 52. Go to step 49
    }

    // 53. Call [[put]] on this with "length", res3-res6+res17
    this.length = len - count + addargs;

    // 54. Return A
    return A;
};

// Ecma 15.4.4.13 Array.prototype.unshift([item1[,item2[,...]]])
// The arguments are prepended to the start of the array, such that their
// order within the array is the same as the order in which they appear
// in the argument list.
Esiply.set_attributes(Array.prototype, "unshift", Esiply.DONT_ENUM);
Array.prototype.unshift = function()
{
    // 1. Call the [[get]] method of this object with argument "length"
    // 2. Call toUint32 on that
    var len = this.length >>> 0;

    // 3. Compute the number of arguments
    var numargs = arguments.length;

    // 4. Let k be len
    // 5. If k is zero, go to step 15
    for (var k = len; k > 0; k--)
    {
        // 6. Call toString(k-1)
        var res6 = String(k-1);

        // 7. Call toString(k+res3-1)
        var res7 = String(k+numargs-1);

        // 8. If this object has a property named by res6, go to step9;
        // but if this object has no property named by res6, then go to 
        // step 12.
        if (res6 in this)
        {
            // 9. Call the [[get]] method of this object with arg res6
            // 10. Call the put method of this with args 7, 9
            this[res7] = this[res6];

            // 11. Go to step 13
        }
        else
        {
            // 12. Call the [[delete]] on this with argument res 7
            delete this[res7];
        }

        // 13. Decrease k by 1
        // 14. Go to step 5
    }

    // 15. Let k be 0
    // 16. get the next argument in the part of the arg list that
    // starts with item1. If there are no more, go to step 21
    for (var k = 0; k < arguments.length; k++)
    {
        // 17. call toString(k)
        // 18. Call the [[put]] method on this with args 17, 16
        this[String(k)] = arguments[k];

        // 19. Increment k by 1
        // 20. Go to step 16
    }

    // 21. call [[put]] on this with "length", res2+res3
    this.length = len + numargs;

    // 22. return res2+res3
    return len+numargs;
};

